package com.zk.algorithm.linkedlist;

import com.zk.algorithm.annotation.JianZhiOffer;
import com.zk.algorithm.bean.ListNode;

/**
 * 链表中环的入口节点
 *
 * @author zk
 */
@JianZhiOffer("23")
public class EntryOfCycledLinkedList {

    // =======================
    // 1 - 确定链表中存在环
    // 2 - 找到环中节点的数目 n
    // 2 - 找到环入口，一个指针 p1 先走 n 步，然后一起走，当 p1 == p2 时，p1 指向入口节点
    // =======================

    public ListNode entryOfLinkedList(ListNode head) {
        LinkedListCycle linkedListCycle = new LinkedListCycle();
        ListNode meetNode = null;

        // 有环，相遇节点一定在环中
        if ((meetNode = meetNode(head)) != null) {
            // 环数量
            int nodeSize = getNodeSizeOfCycledList(meetNode);
            // 找到入口节点
            return findEntry(head, nodeSize);
        }

        return null;
    }

    public ListNode meetNode(ListNode head) {
        if (head == null)
            return null;

        ListNode walker = head;
        ListNode runner = head;

        // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
        //      ↑
        //   walker
        //                ↑
        //             runner
        while (runner.next != null && runner.next.next != null) {
            walker = walker.next;
            runner = runner.next.next;

            if (walker == runner)
                return walker;
        }

        return null;
    }

    private int getNodeSizeOfCycledList(ListNode meetNode) {
        ListNode p = meetNode;
        int count = 1;

        // 再次回到节点，就转了一圈了
        while (p.next != meetNode) {
            p = p.next;
            count++;
        }

        return count;
    }

    private ListNode findEntry(ListNode head, int loopSize) {
        ListNode p1 = head;
        ListNode p2 = head;

        for (int i = 0; i < loopSize; i++) {
            p1 = p1.next;
        }

        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }

}
